package com.facebook.app.server.clustering;

import java.util.ArrayList;
import java.util.List;

import com.facebook.app.shared.clustering.Cluster;
import com.facebook.app.shared.clustering.Clusterable;

public class HierarchicalClusteringWithLists implements ClusteringStrategy {

	private final int numberOfLoopsPerRequest;
	private final ClusterSimilarityStrategy similarityStrategy;

	private ArrayList<Clusterable> clusterElements;

	public HierarchicalClusteringWithLists(ClusterSimilarityStrategy similarityStrategy, List<Clusterable> clusterElements) {
		
		this.similarityStrategy = similarityStrategy;
		
		if (clusterElements instanceof ArrayList) {
			this.clusterElements = (ArrayList<Clusterable>) clusterElements;
		} else {
			this.clusterElements = new ArrayList<Clusterable>(clusterElements);
		}

		// The number of loops per request should depend on
		// the number of elements in the Clusterable list.

		// for testing
		numberOfLoopsPerRequest = Integer.MAX_VALUE;
	}

	@Override
	public List<Clusterable> createClusters() {

		if (clusterElements.size() < 2) {
			return clusterElements;
		}

		List<List<Double>> similarityMatrix = new ArrayList<List<Double>>(
				clusterElements.size() - 1);

		// creating the similarityMatrix:

		for (int i = 0; i < clusterElements.size() - 1; i++) {
			similarityMatrix.add(new ArrayList<Double>(clusterElements.size()
					- i - 1));
		}

		int currentDoubleListIndex = 0;
		for (List<Double> doubleList : similarityMatrix) {
			for (int i = 0; i < clusterElements.size() - currentDoubleListIndex - 1; i++) {
				doubleList.add(similarityStrategy.computeSimilarity(
						clusterElements.get(currentDoubleListIndex),
						clusterElements.get(currentDoubleListIndex + i + 1)));
			}
			currentDoubleListIndex++;
		}

		Double maxSimilarityScore;
		int indexOfHighestScoredPairFirstElement = 0;
		int indexOfHighestScoredPairSecondElement = 0;

		for (int k = 0; k < numberOfLoopsPerRequest
				&& clusterElements.size() > 1; k++) {
			maxSimilarityScore = Double.NEGATIVE_INFINITY;
			
			currentDoubleListIndex = 0;
			// chooses the Clusterable pair with the highest similarity
			for (List<Double> doubleList : similarityMatrix) {
				
				int currentDoubleIndex = currentDoubleListIndex + 1;
				for (Double d : doubleList) {
					if (d > maxSimilarityScore) {
						maxSimilarityScore = d;
						indexOfHighestScoredPairFirstElement = currentDoubleListIndex;
						indexOfHighestScoredPairSecondElement = currentDoubleIndex;
					}
					currentDoubleIndex++;
				}
				currentDoubleListIndex++;
			}

			Clusterable newNode = new Cluster(clusterElements.get(indexOfHighestScoredPairFirstElement),
					clusterElements.get(indexOfHighestScoredPairSecondElement), maxSimilarityScore);

			// important: highestScoredPairFirstElementIndex is always lower
			// than highestScoredPairSecondElementIndex

			clusterElements.set(indexOfHighestScoredPairFirstElement, newNode);
			clusterElements.remove(indexOfHighestScoredPairSecondElement);

			if (clusterElements.size() < 2) {
				break;
			}

			// highestScoredPairSecondElementIndex is equal to
			// similarityMatrix.size()
			// if the last Clusterable in the list was chosen to be
			// clustered.
			if (indexOfHighestScoredPairSecondElement < similarityMatrix.size()) {
				similarityMatrix.remove(indexOfHighestScoredPairSecondElement);
			}

			// Now, the similarities between the second removed element and the
			// remaining ones are removed.
			// The similarities between the new Cluster and the remaining
			// elements are calculated and added.
			for (int i = 0; i < indexOfHighestScoredPairSecondElement; i++) {
				if (i < indexOfHighestScoredPairFirstElement) {
					similarityMatrix.get(i).set(
							indexOfHighestScoredPairFirstElement - i - 1,
							similarityStrategy.computeSimilarity(newNode, clusterElements.get(i)));
				}

				similarityMatrix.get(i).remove(
						indexOfHighestScoredPairSecondElement - i - 1);
			}

			for (int i = 0; i < similarityMatrix.get(indexOfHighestScoredPairFirstElement).size(); i++) {
				similarityMatrix.get(indexOfHighestScoredPairFirstElement).set(
						i,
						similarityStrategy.computeSimilarity(newNode,
								clusterElements
										.get(indexOfHighestScoredPairFirstElement
												+ i + 1)));
			}

		}
		
		clusterElements.trimToSize();

		return clusterElements;
	}

}
